package org.xingole.leetcode.dp.multidimension.jump;

/**
 * Problem Description: 
 * <a href="https://leetcode.com/problems/solving-questions-with-brainpower/description/">
 * Solving Questions With Brainpower
 * </a>
 */
public class SolvingQuestionsWithBrainpower {

     public long mostPointsWithDP1(int[][] questions) {
          // 1. Determine the subproblem substructure.
          // Let dp[i] represents the maximum points that can be earn for the exam.
          int n = questions.length;
          int[] dp = new int[n];

          dp[0] = questions[0][0];
          int maxPoints = dp[0];
          for ( int i = 1; i < n; i++ ) {
               dp[i] = questions[i][0];
               for ( int j = 0; j < i; j++ ) {
                    if ( j + questions[j][1] < i ) {
                         dp[i] = Math.max(dp[i], dp[j] + questions[i][0]);
                    }
               }

               maxPoints = Math.max(dp[i], maxPoints);
          }

          return maxPoints;
     }
     public long mostPointsWithDP2(int[][] questions) {
          // For each question, we can either solve it or skip it.
          // We store for each question the maximum points we can earn if we started 
          // the exam on that question, denoted dp[i].
          int n = questions.length;
          long[] dp = new long[n + 1];
          
          // Base case: dp[n] = 0.

          // If we skip a question, then the answer for it will be the same as the 
          // answer for the next question.
          // dp[i] = dp[i+1];

          // If we solve a question, then the answer for it will be the points of the 
          // current question plus the answer for the next solvable question.
          // dp[i] = points[i] + dp[i+brainpower[i]+1]
          
          // The maximum of these two values will be the answer to the current question.
          // Therefore, the dp[i] = max(dp[i+1], points[i] + dp[i+brainpower[i]+1]).
          for ( int i = n - 1; i >= 0; --i ) {
               dp[i] = Math.max(
                    dp[i + 1], 
                    questions[i][0] + dp[Math.min(n, i + questions[i][1] + 1)]
               );
          }

          return dp[0];

     }

}
